package gold.digger;

import gold.vo.TreeNode;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC236 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (null == root || root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        if (null != left && left != p && left != q) {//left is its common ancestor
            return left;
        }
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (null != right && right != p && right != q) {
            return right;
        }

        if (left != null && right != null) {
            return root;
        }

        return (left == null) ? right : left;
    }


    public static void main(String[] args) {

    }
}
